#include <cstdio>

int prime[ 1000000 ], cnt;
bool use[ 10000001 ];

void init( )
{
    int i, j;
    for ( i = 2; i <= 10000000; i++ )
        if ( !use[ i ] )
        {
            prime[ cnt++ ] = i;
            for ( j = i * 2; j <= 10000000; j += i )
                use[ j ] = 1;
        }
}

int main( )
{
    int t, n, m, c, i, p;
    __int64 ans;
    init( );
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d%d", &n, &m);
        c = 0;
        for ( i = 0; prime[ i ] <= n && i < cnt; i++ )
            c += n / prime[ i ];
        p = ans = 1;
        while ( p <= c ) p <<= 1;
        p >>= 1;
        while ( p )
        {
            ans = ans * ans % m;
            if ( p & c )
                ans = ans * 2 % m;
            p >>= 1;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}
